/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package genetic_algorithm;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * A generic Genetic Algorithm class.
 * @author pborrego
 */
public abstract class GA {
    public final static int FLIP = 0;
    public final static int INSERT = 1;
    public final static int DELETE = 2;
    protected ArrayList<Chromosome> population;
    protected ArrayList<Float> fitness;
    protected ArrayList<Integer> rawFitness;
    protected float mutationRate;

    public void run(int generations)
    {
        int popSize = this.population.size();
        Chromosome dad, mom, child;
        ArrayList<Chromosome> newPop = new ArrayList<Chromosome>();

        for(int i=0; i < generations; i++)
        {
            for(int j=0; j<popSize; j++)
            {
                do
                {
                    this.updateFitness();
                    dad = this.selectChromosome();
                    mom = this.selectChromosome();

                    child = this.crossover(dad, mom);
                    child = this.mutate(child);
                } while(isValidChromosome(child));
                newPop.add(child);
            }

            Iterator<Chromosome> newPopIt = newPop.iterator();
            this.population.clear();
            while(newPopIt.hasNext())
            {
                this.population.add(newPopIt.next());
            }
            newPop.clear();
        }
    }

    /**
     * Creates a population of chromosomes with random genes.
     * This needs to be created by implementer.
     */
    public void populate() {}

    /**
     * This determines if a chromosom is valid. For some problems it is possible
     * to have invalid solutions be generated. This is a way of pruning that. The
     * implementer should override this.
     * @param c -- A chromosome that should be tested.
     * @return -- True if the chromosome validates else False for invalid chromosomes.
     */
    public boolean isValidChromosome(Chromosome c) {
        return true;
    }

    /**
     * Takes two parent chromosomes and returns a new chromosome that is a mixture of the two.
     * @param dad -- A parent chromosome
     * @param mom -- A parent chromosome
     * @return -- A child chromosome which is a mixture of the two parents.
     */
    protected Chromosome crossover(Chromosome dad, Chromosome mom) {
        Chromosome child = dad;
        ArrayList<Allele> dadAlleles = dad.splitChromosome(2);
        ArrayList<Allele> momAlleles = mom.splitChromosome(2);

        child.setGenes( Allele.Combine(
            dadAlleles.get(0).getGenes(),
            momAlleles.get(momAlleles.size() - 1).getGenes()
        ));

        return child;
    }

    /**
     * Takes a chromosome and mutates its data determined by the mutationRate.
     * @param c -- The chromosome to apply the mutate operator to.
     * @return -- A new chromosome that has been mutated or the same chromosome
     * that was passed in.
     */
    protected Chromosome mutate(Chromosome c) {

        if(Math.random() <= this.getMutationRate())
        {
            c.mutate(Chromosome.randomMutationType());
        }

        return c;
    }

    /**
     * Updates the cumulative fitness of the population.
     */
    protected void updateFitness() {
        float total = 0;

        this.rawFitness.clear();
        this.fitness.clear();

        Iterator<Chromosome> i = this.population.iterator();
        while(i.hasNext()) {
            this.rawFitness.add(i.next().fitness());
            total += rawFitness.get(rawFitness.size() - 1).intValue();
        }

        Iterator<Integer> j = rawFitness.iterator();
        while(j.hasNext()) {
            this.fitness.add(j.next() / total);
        }
    }

    /**
     * Randomly selects a chromosome using the cumulative fitness of the population.
     * This ensures that the better the fitness the more likely that the
     * chromosome is picked.
     * @return -- A random chromosome from the population.
     */
    protected Chromosome selectChromosome() {
        double probablity = Math.random();
        double curProb = 0;
        int i = -1;

        while(probablity > curProb)
        {
            i++;
            curProb += this.fitness.get(i);
        }

        return this.population.get(i);
    }

    /**
     * Returns the Chromosome with the best fitness.
     * @return -- A chromosome from the population with the best fitness.
     */
    protected Chromosome bestChromosome() {
        int best = 0;
        int popSize = this.population.size();

        for(int i=0; i<popSize; i++)
        {
            if(this.rawFitness.get(i) > this.rawFitness.get(best))
            {
                best = i;
            }
        }

        return this.population.get(best);
    }

    /**
     * Returns the cumulative fitness of the population.
     * @return -- A vector of the cumulative fitness of the population
     */
    public ArrayList<Float> getFitness() {
        return fitness;
    }

    /**
     * Returns the mutation rate of the algorithm. This represents how often a
     * chromosome is mutated. The higher the number the more frequent chromosomes
     * are mutated.
     * @return -- A floating point number representing the mutation rate.
     */
    public float getMutationRate() {
        return mutationRate;
    }

    /**
     * Sets the mutation rate of the algorithm. This number should be between 0
     * and 1.
     * @param mutationRate -- A floating point number between 0 and 1.
     */
    public void setMutationRate(float mutationRate) {
        this.mutationRate = mutationRate;
    }

    /**
     * Returns the population of chromosomes.
     * @return -- A vector of Chromosomes.
     */
    public ArrayList<Chromosome> getPopulation() {
        return population;
    }
}
